/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/dices-sum
   @Language: C++
   @Datetime: 19-03-11 11:58
   */


// Time 75ms
class Solution {
public:
	/**
	 * @param n an integer
	 * @return a list of pair<sum, probability>
	 */
	vector<pair<int, double> > dicesSum(int n) {
		// Write your code here
		unordered_map<int,double> dices;
		for(int i=0; i<6; dices[++i]=1.0/6);
		while(--n){
			unordered_map<int,double> tmp;
			for(pair<int,double> p : dices){
				for(int i=1; i<7; i++){
					tmp[p.first+i] += p.second/6;
				}
			}
			dices = tmp;
		}
		// sort
		map<int,double> res;
		for(pair<int,double> p : dices)
			res[p.first] = p.second;

		vector<pair<int,double> > vp;
		for(pair<int,double> p : res)
			vp.push_back(make_pair(p.first,p.second));
		return vp;
	}
};
